package priority_queue.leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可
 */

class IntegerReverse implements Comparator<Integer>{

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}

public class Num17_14 {
    public int[] smallestK(int[] arr, int k) {
        int[] ret=new int[k];
        if (arr.length==0||k==0){
            return ret;
        }
        //JDK是默认使用最小堆，所以我们要将其改造为最大堆,通过比较器实现
        Queue<Integer> queue=new PriorityQueue<>(new IntegerReverse());
        //遍历集合，堆中只保存k个元素
        for (int i = 0; i < arr.length; i++) {
            if (queue.size()<k){
                //此时堆中的元素<k，就直接添加新元素
                queue.offer(arr[i]);
            }else {
                //此时堆中的元素=k
                int max=queue.peek();
                if (arr[i]<max){
                    queue.poll();
                    queue.offer(arr[i]);
                }
            }

        }
        int i=0;
        while (!queue.isEmpty()){
            ret[i]=queue.poll();
            i++;
        }
        return ret;
    }
}
